package link;

import array.ListNode;


public class SortList148 {
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode mid = getMid(head);
        ListNode node = mid.next;
        mid.next=null;
        ListNode node1 = sortList(head);
        ListNode node2 = sortList(node);
        return combination(node1,node2);
    }


    private ListNode combination(ListNode first, ListNode second) {
        ListNode f_temp = first;
        ListNode s_temp = second;
        ListNode idle = new ListNode();
        ListNode temp = idle;
        while (f_temp!=null&&s_temp!=null){
            if(f_temp.val>s_temp.val){
                temp.next= s_temp;
                s_temp=s_temp.next;
            }else {
                temp.next=f_temp;
                f_temp=f_temp.next;
            }
            temp=temp.next;
        }
        if(f_temp!=null){
            temp.next=f_temp;
        }
        if(s_temp!=null){
            temp.next = s_temp;
        }
        return idle.next;
    }

    private ListNode getMid(ListNode begin) {
        if(begin==null||begin.next==null){
            return begin;
        }
        ListNode temp = new ListNode();
        temp.next = begin;
        ListNode quick = temp;
        ListNode slow = temp;
        while (quick!=null&&quick.next!=null){
            quick = quick.next.next;
            slow = slow.next;
        }
        return slow;
    }

//    public ListNode sortList(ListNode head) {
//        int size = 0;
//        ListNode temp = head;
//        while (temp != null) {
//            temp = temp.next;
//            size++;
//        }
//
//        ListNode idle = new ListNode();
//        idle.next = head;
//        int k = 1;
//        while (k < size) {
//            ListNode ttemp = idle;
//            while (ttemp != null) {
//                ListNode first = ttemp;
//                int ssize = 0;
//                while (ssize != k && ttemp != null) {
//                    ttemp = ttemp.next;
//                    ssize++;
//                }
//                ListNode second = ttemp;
//
//                sort(first, second, k);
//            }
//
//            k = 2 * k;
//        }
//        return idle.next;
//    }
//
//    private void sort(ListNode first, ListNode second, int k) {
//        if(second==null){
//            return;
//        }
//        int first_index = 0;
//        int second_index = 0;
//        while (first_index != k && second_index != k
//                && first != null && first.next != null
//                && second != null && second.next != null) {
//            if (first.next.val > second.next.val) {
//                ListNode temp = first.next;
//                first.next = second.next;
//                second.next = second.next.next;
//                first.next.next = temp;
//                second_index++;
//            } else {
//                first.next = first.next.next;
//                first_index++;
//            }
//        }
////        ListNode tail = second;
////        while (second_index != k && tail != null ) {
//////            ListNode temp = first.next;
////            tail = tail.next;
////        }
////        first.next = tail;
//    }


}
